package work;

import java.util.HashMap;
import java.util.Map;

/**
 * 元素和为目标值的子矩阵数量
 * 时间复杂度：
 * 思路：前缀和+哈希表
 * 枚举子矩阵的上下边界，并计算出该边界内每列的元素和，则原问题就转换成了如下一维问题：
 *      给定一个整数数组和一个整数target，计算该数组中子数组和等于target的子数组个数（和为k的子数组subarraySum）
 */
public class NumSubmatrixSumTarget {

    public int numSubmatrixSumTarget(int[][] matrix, int target) {
        int ans = 0;
        int m = matrix.length;//行
        int n = matrix[0].length;//列
        for(int i = 0; i < m; i++){//枚举上边界
            int[] sum = new int[n];
            for (int j = i; j < m; j++){//枚举下边界
                for(int c = 0; c < n; c++){
                    sum[c] += matrix[j][c];//更新每列的元素和
                }
                ans += subarraySum(sum, target);
            }
        }
        return ans;
    }
    private int subarraySum(int[] nums, int k){//和为k的子数组
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        int preSum = 0;//前缀和
        int res = 0;//计数
        for (int i = 0; i < nums.length; i++){
            preSum += nums[i];
            if(map.containsKey(preSum - k)){//注意点：判断要放在添加前面，否则当k=0时，就会把自身加一遍
                res += map.get(preSum - k);
            }
            if(map.containsKey(preSum)){
                map.put(preSum, map.get(preSum) + 1);
            }else {
                map.put(preSum, 1);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[][] matrix = new int[][]{{0,1,0},
                                    {1,1,1},
                                    {0,1,0}};
        int ans = new NumSubmatrixSumTarget().numSubmatrixSumTarget(matrix, 0);
        System.out.println(ans);
    }
}
/**
 * 输入：matrix = [[1,-1],[-1,1]], target = 0
 * 输出：5
 */
